This invention relates primarily to a class of digital communication systems known as asynchronous transfer mode (ATM) switching systems and generally to intercomputer communications architectures. The invention more specifically relates to systems and methods for detecting data congestion within an ATM network.
A building block in a switch-fabric architecture ATM switch system is a structure known as a switch element. A switch element provides packet signal routing from one of a plurality of input ports to one or more of a plurality of output ports by maintaining an array of crosspoints for connecting any input port to any output port. Switch elements may be aggregated in various patterns to provide arbitrarily large N by N possible interconnection of input ports to output ports.
Problems arise where the receiving port cannot assimilate information as fast as it is delivered or where the priority of the traffic varies. A "brute-force" technique for handling the queuing problem is to provide sufficient data storage at each possible crosspoint in the switch element. If the amount of data accumulated at the crosspoint exceeds the capacity of the data storage, data is discarded, thus forcing the destination port to request that data be resent.
An alternative solution is discussed in detail in co-assigned U.S. Pat. No. 5,583,861 entitled ATM ARCHITECTURE AND SWITCHING ELEMENT. A difference in that ATM architecture over most prior systems is the use of a shared pool of memory for storing cells. A shared pool more effectively utilizes available memory.
Use of a shared pool of memory also creates an opportunity for more effective and sophisticated congestion management in an ATM architecture. Prior ATM systems generally measured congestion only crudely, either measuring congestion on just a physical device basis or according to just one or a few parameters in a device, such as priority. Some prior art systems attempted to infer congestion by examining traffic flow in particular channels of the network or did not measure congestion at all, but instead made a determination to discard buffered cells when shared buffers were full.
How an ATM network manages congestion is an important characteristic that affects overall performance. In general, it is desirable for an ATM switch to rarely drop a cell due to congestion. In order to achieve this, the network must be able to signal to transmitters that they must halt or slow down transmission when congestion begins to occur.
Congestion occurs when two cells are directed to the same output at the same time. In general, one of the cells will be stored temporarily in a buffer (or queue) associated with one of the ATM devices and will be output during a subsequent cell cycle. Congestion can also occur because stored cells at an intermediate resource in the ATM network, such as at a particular input routing table (IRT) or output routing table (ORT), exceeds the physical memory (buffer) storage capacity of that device.
Prior Art References
U.S. Pat. No. 5,280,470 (Buhrke), filed Feb. 3, 1993, priority Nov. 21, 1990, as a further example, describes a congestion management in broadband ISDN cell networks where overload is detected in a network switch and then a routine is performed to determine which virtual channels to slow down (FIG. 4) in order to relieve congestion. Buhrke does not monitor congestion in a particular virtual channel, but instead infers congestion by monitoring transmission rates. Buhrke does not monitor congestion in several dimensions on an ongoing basis.
U.S. Pat. No. 5,233,606 (Pashan), filed Aug. 2, 1991, discusses controlling shared-buffer-memory overflow in a multipriority environment that does not measure congestion at all but instead waits until all buffer memories are used up and then determines from which memory a cell should be flushed. (See, for example, the abstract, "It initially allows output-port queues to completely consume the buffer memory. Thereafter, when an additional incoming cell is received for which there is no room in the buffer memory, the lengths of all of the queues of each output port are individually summed and compared to determine which port has the greatest number of buffered cells. A buffered ATM cell is discarded from the lowest priority non-empty queue of that port." Pashan teaches away from actually measuring congestion in that, instead of measuring congestion, Pashan allows a buffer to fill up and then discards cells from that buffer.
U.S. Pat. No. 5,313,454 (Bustini), filed Apr. 1, 1992, for example, describes a congestion control for cell networks where congestion is monitored by measuring queue lengths at network nodes. Because congestion is monitored in only one dimension at a particular buffer pool memory, the congestion detection threshold must be set very low as compared with the possible capacity of the buffers. For example, the patent states, "The PQth threshold is normally set at four kilobytes, a fraction of the 64 kilobyte queue capacity." 13:52-54.
U.S. Pat. No. 5,367,520 (Cordell), filed Nov. 25, 1992, discusses a multiple plane switch fabric. A number of problems must be solved in order to efficiently and correctly transmit data from multiple sources to multiple destinations across such a multiple plane fabric. FIG. 5 of the '520 patent illustrates a mechanism for handling two of these problems: (1) spreading cells out over multiple planes in the switch fabric, and (2) maintaining cells in order through the switch fabric so that if stream of cells 1-10 are queued to a particular destination A, cell A1 is always delivered before cell A2. The backpressure feedback is discussed at 16:31 et seq. The discussed scheme is limited to measuring congestion in the output buffers only. The reference states that "In practice, however, it is probably satisfactory to make all cells destined to that queue's entire Output Buffer Group of 16 queues wait, resulting in a brief 0.2% reduction in switch throughput." (16:52-55)
U.S. Pat. No. 5.359,592 (Corbalis), filed Jun. 25, 1993, describes a congestion control in an ATM device where cell counts are kept on a per cell queue basis only, and these counts are compared to up to three different thresholds. Though Corbalis sets many different threshold levels, levels are set in only one dimension.
Cooper, C. A. and Park, K. I. (Cooper), "Toward a Broadband Congestion Control Strategy," I.E.E.E. Network Magazine, May 1990, is a survey article that discusses a possibility of congestion control strategies where ATM cells may be processed in accordance with multilevel priorities. Traffic Characterization, Admission Control, and Policing are discussed. A strategy of many-dimensional congestion measuring in a shared buffer is not discussed.
Oshima, K. et al, (Oshima), "A New Switch Architecture Based on STS-Type Shared Buffering and its LST Implementation," XIV International Switching Symposium, Yokohama, Japan, October 1992 discusses an ATM architecture with a partially shared buffer that does not discuss congestion measurement in shared buffers.
Badran, H. F. and Mouftah, H. T. (Badran I), "Head of Line Arbitration in ATM Switcher with Input-Output Buffering and Backpressure Control," GLOBECOM '91, I.E.E.E., discuss a backpressure mechanism that uses two queue specific criteria (queue length and input-queue age) and two cell-specific criteria (time of joining input queues and time of arrival to the head-of-line position) to resolve head-of-line contention.
Badran, H. F. and Mouftah, H. T. (Badran II), "Input-Output-Buffered ATM Switches with Delayed Backpressure Mechanisms," CCECE/CCGEI '93, I.E.E.E., discuss a delayed backpressure feedback mechanism that sets two levels (Level1 and Level2) for measuring congestion on one dimension of the output queue only (see FIG. 1).
More sophisticated and finer congestion management on multiple dimensions would be desirable in a shared memory system because when congestion is measured and monitored at finer levels of detail, the system can allow individual types of traffic to use more of the shared resources while still ensuring that sufficient resources will be available to provide guaranteed service to higher priority traffic. However, increased levels of congestion detection and management require increased circuit and processing overhead and could reduce processing speed.
Increasing demands for communications speed and capacity have created a need for higher performance ATM architectures as described in U.S. Ser. No. 60/033,029. This architecture differs from the architecture in the parent patent applications in that the primary shared memory areas are associated with an input routing table (IRT) and output routing table (ORT). Shared buffer memory associated with individual switch elements are generally used only when handling multicast traffic. The architecture is different also in that it provides for a number of virtual outputs (VOs) for each physical output from an ORT and virtual inputs (VIs) for each physical input to an IRT. In one specific embodiment, the ORT and IRT are combined into a single device referred to as a Quad Routing Table (QRT). The QRT may be used in connection with a switch fabric constructed of switch elements (SEs) as described in the parent applications or may be used in connection with a switch fabric made up of update quad switch elements (QSEs) described in U.S. Ser. No. 60/033,029.
What is needed is a congestion management scheme for an ATM architecture having substantial shared resources that allows effective use of system resources while able to guarantee service to certain traffic classes.